//
// Created by Jeremy Shiqi Zhang on 2020/7/15.
//

#include "function.h"

int binary_insert(vector<int> &v, int data) {
    if(v.empty()){
        v.push_back(data);
        return 0;
    }
    auto first = v.begin();
    auto last = v.end();
    int ele;
    int count = distance(first,last);
    int step;
    while (count>0)
    {
        auto it = first;
        step=count/2;
        advance (it,step);
        ele = *it;
        if (data >= ele) {
            first=++it;
            count-=step+1;
        }
        else count=step;
    }
    int cur = -1;
    if(first!=v.begin())
        cur = *(first-1);
    int idx = distance(v.begin(),first);
    if(cur!=data){
        v.insert(first,data);
        return idx;
    }
    else{
        return -1;
    }
}

int binary_find(vector<int> &v, int data) {
    if(v.empty()){
        return -1;
    }
    auto first = v.begin();
    auto last = v.end();
    int ele;
    int count = distance(first,last);
    int step = count;
    while (count>0)
    {
        auto it = first;
        step=count/2;
        advance (it,step);
        ele = *it;
        if (data > ele) {
            first=++it;
            count-=step+1;
        }
        else count=step;
    }
    int i = distance(v.begin(),first);
    if(i < v.size() && data == *first)
        return i;
    return -1;
}

void binary_remove(vector<int> &v, int data){
    if(v.empty()){
        return;
    }
    auto first = v.begin();
    auto last = v.end();
    int ele;
    int count = distance(first,last);
    int step;
    while (count>0)
    {
        auto it = first;
        step=count/2;
        advance (it,step);
        ele = *it;
        if (data > ele) {
            first=++it;
            count-=step+1;
        }
        else count=step;
    }
    if(data==*first && first!=v.end()){
        v.erase(first);
    }
}
